package util.preprocessing;

import java.sql.Timestamp;
import java.util.Arrays;
import java.util.Enumeration;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;

import util.io.FileInput;
import util.string.StringAnalysis;


public class sessionAnalysis {

	/**
	 * @param args
	 */

	static  int QUERY_POS = 1;

	static int USER_POS = 2;
	static final int REFORMULATIONS=8;
	static final int SESSION_POS = 0;
	static final int SPELLING_CORRECTION = 6;
	
	
	static  int URL_POS = 6;
	static  int RANK_POS = 5;
	static  int TIME_POS = 4;
	
	
	static final int NEW_QUERY = 0;
	static final int WORD_ADDED = 1;

	static final int WORD_REMOVED = 2;
	static final int WORD_CHANGED = 3;
	static final int MORE_RESULTS = 4;

	static final int PREVIOUS_QUERY = 5;
	static final int END_SESSION = 7;
	
	static final int EDIT_THRESHOLD = 2;
	
	
	
	static Hashtable<Integer, ReformulationStat> reformulation_stats= new Hashtable<Integer, ReformulationStat>();
	
	static final int ERROR = -1;

	/**
	 * Returns true if at least 1 word was added to the previous query at
	 * position pos of the session
	 * 
	 */
	public static boolean wordAdded(LinkedList<String[]> session, int pos) {
		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);
		if (current_query[QUERY_POS].startsWith(previous_query[QUERY_POS]) &&
		!current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;
		}
		return false;
	}
	
	
	public static boolean spellingCorrection(LinkedList<String[]> session,
			int pos) {
		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);
		if (StringAnalysis.getEditDistance(current_query[QUERY_POS],
				previous_query[QUERY_POS]) <= EDIT_THRESHOLD) {
			return true;
		}
		return false;
	}

	private static boolean wordAdded(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		
		
		LinkedList<String[]> miniSession = new LinkedList<String[]>();
		
		
		miniSession.addLast(queryA);
		miniSession.addLast(queryB);
		
		return wordAdded(miniSession, miniSession.size()-1);
		
		
	}
	
	

	/**
	 * Returns true if at least 1 word was removed to the previous query at
	 * position pos of the session
	 * 
	 */
	public static boolean wordRemoved(LinkedList<String[]> session, int pos) {

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		if (previous_query[QUERY_POS].startsWith(current_query[QUERY_POS]) &&

		!current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;
		}

		return false;
	}

	public static boolean isNewQuery(LinkedList<String[]> session, int pos) {

		if (pos == 0)
			return true;

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		String a[] = previous_query[QUERY_POS].split("\\s+");
		String b[] = current_query[QUERY_POS].split("\\s+");

		for (int i = 0; i < a.length; i++) {

			for (int j = 0; j < b.length; j++) {

				if (a[i].trim().equals(b[j].trim())) {

					return false;
				}

			}
		}

		return true;

	}

	/**
	 * At least one word of the current query is written in the previous query
	 * 
	 * @param session
	 * @param pos
	 * @return
	 */
	public static boolean changedWordsInQuery(LinkedList<String[]> session,
			int pos) {

		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		String a[] = previous_query[QUERY_POS].split("\\s+");
		String b[] = current_query[QUERY_POS].split("\\s+");

		for (int i = 0; i < b.length; i++) {

			for (int j = 0; j < a.length; j++) {

				if (b[i].trim().equals(a[j].trim())) {

					return true;
				}

			}
		}

		return false;

	}

	
	
	
	public static int evaluateCurrentQuery(Hashtable<String,HashSet<Integer>> query_pos, LinkedList<String[]> session, int pos) {

		
		
		
		
		if (pos < session.size()) {
			
			
			if(pos>1 && (session.get(pos-1)[QUERY_POS].trim().equals("-")
					
					|| session.get(pos)[QUERY_POS].trim().equals("-"))
			){
				
				return -1;
				
			}
			
			
			
			
			
			
			
			
			
			

			if (moreResultsSameQuery(session, pos)) {

				return MORE_RESULTS;

			}

			else if (returnToPreviousQuery(session, pos,query_pos)) {

				return PREVIOUS_QUERY;

			}

			else if (isNewQuery(session, pos)) {
				return NEW_QUERY;
			}else if(spellingCorrection(session,pos)){
				
				return SPELLING_CORRECTION;
			}

			else if (wordAdded(session, pos)) {

				return WORD_ADDED;
			} else if (wordRemoved(session, pos)) {
				return WORD_REMOVED;

			} else if (changedWordsInQuery(session, pos)) {

				return WORD_CHANGED;
			} else {

				return ERROR;
			}

		} else {
			return END_SESSION;

		}
	}

	
	
	public static int evaluateCurrentQuery(String[] queryA, String[] queryB) {

		if (moreResultsSameQuery(queryA, queryB)) {

			return MORE_RESULTS;

		}

		else if (isNewQuery(queryA, queryB)) {
			return NEW_QUERY;
		}

		else if (wordAdded(queryA, queryB)) {

			return WORD_ADDED;
		} else if (wordRemoved(queryA, queryB)) {
			return WORD_REMOVED;

		} else if (changedWordsInQuery(queryA, queryB)) {

			return WORD_CHANGED;
		} else {

			return -1;
		}
		
		

	}
	
	

	private static boolean isNewQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		
		LinkedList<String[]> miniSession = new LinkedList<String[]>();
		
		
		miniSession.addLast(queryA);
		miniSession.addLast(queryB);
		
		return isNewQuery(miniSession, miniSession.size()-1);

	}

	private static boolean changedWordsInQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		
		LinkedList<String[]> miniSession = new LinkedList<String[]>();
		
		
		miniSession.addLast(queryA);
		miniSession.addLast(queryB);
		
		return changedWordsInQuery(miniSession, miniSession.size()-1);
		
	}

	private static boolean wordRemoved(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		LinkedList<String[]> miniSession = new LinkedList<String[]>();

		miniSession.addLast(queryA);
		miniSession.addLast(queryB);

		return wordRemoved(miniSession, miniSession.size() - 1);
	}

	private static boolean moreResultsSameQuery(String[] queryA, String[] queryB) {
		// TODO Auto-generated method stub
		
		
		LinkedList<String[]> miniSession = new LinkedList<String[]>();
		
		miniSession.addLast(queryA);
		miniSession.addLast(queryB);
		
		
		return moreResultsSameQuery(miniSession,miniSession.size()-1);
	}

	public static boolean moreResultsSameQuery(LinkedList<String[]> session,
			int pos) {

		
		
		if(pos==0) return false;
		
		String previous_query[] = session.get(pos - 1);
		String current_query[] = session.get(pos);

		if (current_query[QUERY_POS].equals(previous_query[QUERY_POS])) {
			return true;
		}

		return false;

	}

	public static boolean returnToPreviousQuery(LinkedList<String[]> session,
			int pos, Hashtable<String, HashSet<Integer>> query_pos) {

		if (pos < session.size() && pos > 1) {

			String current = session.get(pos)[QUERY_POS].trim();
			HashSet<Integer> previous_queries = query_pos.get(current);

			Iterator<Integer> iter = previous_queries.iterator();

			while (iter.hasNext()) {

				Integer i = iter.next();
				if (i < pos - 1) {

					return true;

				}

			}

		}

		return false;

	}

	public static long[][] getStateTransitionMatrix(String queryLog) {

		long matrix[][] = new long[REFORMULATIONS][REFORMULATIONS];

		FileInput in = new FileInput(queryLog);

		String previous_line = in.readString();
		String previous_split[] = previous_line.trim().split("\t");
		LinkedList<String[]> session = null;
		while (previous_line != null) {

			session = new LinkedList<String[]>();

			session.addLast(previous_split);

			String current_line = in.readString();
			String current_split[] = null;
			if (current_line != null) {
				current_split = current_line.trim().split("\t");
			}

			while (current_split != null
					&& previous_split[0].trim().equals(current_split[0].trim())) {

				// update previous line
				previous_line = current_line;
				previous_split = current_split;

				// update session lines
				session.addLast(previous_split);

				// update current line
				current_line = in.readString();
			//	System.out.println("aqui: " + current_split[0] + " current line:" + current_line);
				if (current_line != null)
					current_split = current_line.trim().split("\t");
				else
					current_split = null;

			}

			// Process current session

			updateTransitionMatrix(matrix, session);

			previous_line = current_line;
			previous_split = current_split;

		}

		// update matrix with the last section (non included in the previous
		// loop)

		// updateTransitionMatrix(matrix, session);

		printMatrix(matrix);
		
	//	printStats();

		return matrix;

	}

	
	private static void printStats() {
		// TODO Auto-generated method stub

		Enumeration<Integer> enu = reformulation_stats.keys();

		while (enu.hasMoreElements()) {

			Integer key = enu.nextElement();

			ReformulationStat stat = reformulation_stats.get(key);

			System.out.println(key + 
					"\t" + stat.clickClick + 
					"\t" + stat.clickSkip + 
					"\t" + stat.skipClick 
					+ "\t"+ stat.skipSkip +
					"\t" + stat.equalDomain + "\t"
					+ (float) stat.rank_difference / (float) stat.items_rank
					+ "\t" + (float) stat.time_difference / (float) stat.items
					+ "\t" + stat.items);

		}

	}


	/**
	 * Expand query line with dummy session: Session is 
	 * 
	 */
	private static String expandQueryLine(String line){
		
		
		if(line==null ) return null;
		String temp =line;
		return  "0"+ "\t"+temp;
		
	}
	
	public static void getGoals(String queryLog, boolean dummySession) {

		FileInput in = new FileInput(queryLog);

		String previous_line = in.readString();

		
		if (dummySession){
			previous_line = expandQueryLine(previous_line);
			QUERY_POS= QUERY_POS+1;
			 URL_POS = URL_POS+1;
			 RANK_POS = RANK_POS+1;
			 TIME_POS = TIME_POS+1;
		}
		
		String previous_split[] = previous_line.trim().split("\t");
		LinkedList<String[]> session = null;

		LinkedList<LinkedList<String[]>> goals = null;
		while (previous_line != null) {

			session = new LinkedList<String[]>();

			session.addLast(previous_split);

			String current_line = in.readString();

			if (dummySession)
				current_line = expandQueryLine(current_line);

			String current_split[] = null;
			if (current_line != null) {
				current_split = current_line.trim().split("\t");
			}
		

			while (current_split != null
					&& previous_split[SESSION_POS].trim().equals(current_split[SESSION_POS].trim())) {

				// update previous line
				previous_line = current_line;
				previous_split = current_split;

				// update session lines
				session.addLast(previous_split);

				// update current line

				current_line = in.readString();

				if (dummySession)
					current_line = expandQueryLine(current_line);

				if (current_line != null)
					current_split = current_line.trim().split("\t");
				else
					current_split = null;

			}

			// Process current session
			goals = getGoalsPerSession(session);
			printGoals(goals);

			previous_line = current_line;
			previous_split = current_split;

		}

	}

	
	
	private static void printGoals(LinkedList<LinkedList<String[]>> goals) {
		// TODO Auto-generated method stub

		
		
		
		System.out.println(goals.size());
		for (int i = 0; i < goals.size(); i++) {

			LinkedList<String[]> current_goal = goals.get(i);
			for (int j = 0; j < goals.get(i).size(); j++) {

				String[] current_query = current_goal.get(j);
				
				System.out.print(current_query[SESSION_POS] +"\t" + i);
				for (int k = 1; k < current_query.length; k++) {
					if(k!=SESSION_POS)
					System.out.print("\t" + current_query[k]);

				}

				System.out.println("");

			}

		}

	}

	private static void printMatrix(long[][] matrix) {
		// TODO Auto-generated method stub

		for (int i = 0; i < matrix.length - 1; i++) {

			for (int j = 0; j < matrix[i].length; j++) {

				System.out.print(matrix[i][j] + "\t");

			}
			System.out.println("");

		}

	}

	
	private static Hashtable<String, HashSet<Integer>> initQueryPos(
			LinkedList<String[]> session) {

		Hashtable<String, HashSet<Integer>> query_pos = new Hashtable<String, HashSet<Integer>>();

		for (int i = 0; i < session.size(); i++) {
			if(session.get(i).length>QUERY_POS){
			
			
			String query = session.get(i)[QUERY_POS].trim();
			HashSet<Integer> set;
			if (query_pos.containsKey(query)) {

				set = query_pos.get(query);
				set.add(i);

			} else {
				set = new HashSet<Integer>();
				set.add(i);

			}

			query_pos.put(query, set);
		}
		}
		
		return query_pos;

	}
	
	
	private static void updateTransitionMatrix(long[][] matrix,
			LinkedList<String[]> session) {
		// TODO Auto-generated method stub

		// Init Hashtable with position of unique queries inside the session
		Hashtable<String, HashSet<Integer>> query_pos = initQueryPos(session);

		if (session != null && session.size() > 0) {

			int init = evaluateCurrentQuery(query_pos, session, 0);

			for (int i = 1; i < session.size() + 1; i++) {

				int current = evaluateCurrentQuery(query_pos, session, i);

				if (current != -1) {

					if (reformulation_stats.containsKey(current)) {
						updateReformulationStats(session, i,
								reformulation_stats.get(current), current);
					} else {

						ReformulationStat stat = new ReformulationStat();
						updateReformulationStats(session, i, stat, current);
						reformulation_stats.put(current, stat);

					}

					matrix[init][current]++;

					init = current;
				}
			}

		}

	}

	private static void updateReformulationStats(LinkedList<String[]> session,
			int i, ReformulationStat reformulationStat, int reformulation_type) {
		// TODO Auto-generated method stub

		if (i != 0 && session.size() > i) {

			String[] original = session.get(i - 1);
			String reformulation[] = session.get(i);


			if (original.length > RANK_POS) {

				// Case click click
				if (reformulation.length > RANK_POS && checkIfNumber(reformulation[RANK_POS].trim())
						
						&& checkIfNumber(original[RANK_POS].trim())
				) {

					
					reformulationStat.rank_difference += (Integer
							.valueOf(reformulation[RANK_POS].trim()) - Integer
							.valueOf(original[RANK_POS].trim()));

					reformulationStat.items_rank++;

					reformulationStat.clickClick++;
					// Case click skip
				} else {

					reformulationStat.clickSkip++;

				}

			} else {
				// case skip click
				if (reformulation.length > RANK_POS) {
					reformulationStat.skipClick++;
				}
				// case skip skip
				else {
					reformulationStat.skipSkip++;
				}
			}

			Timestamp a = java.sql.Timestamp.valueOf(reformulation[TIME_POS]
					.trim());
			Timestamp b = java.sql.Timestamp.valueOf(original[TIME_POS].trim());

			double t = a.getTime() / 1000 - b.getTime() / 1000;

			
			Long aa = new Long((long)t);
			//reformulationStat.time.add(aa);
			reformulationStat.time_difference += t;
			reformulationStat.items++;

		}

	}

	/**
	 * 
	 * Segment each session by detecting 'topic related queries' based on edit
	 * distance, word distance, among others
	 * 
	 * @param session
	 *            List of query entries representing the session
	 * @return List of goals (which is a list of query entries)
	 */
	
	  public static  boolean checkIfNumber(String in) {
	        
	        try {

	            Integer.parseInt(in);
	        
	        } catch (NumberFormatException ex) {
	            return false;
	        }
	        
	        return true;
	    }
	public static LinkedList<LinkedList<String[]>> getGoalsPerSession(
			LinkedList<String[]> session) {

		LinkedList<LinkedList<String[]>> goals = new LinkedList<LinkedList<String[]>>();

		Hashtable<Integer, HashSet<Integer>> goals_index = new Hashtable<Integer, HashSet<Integer>>();
		Hashtable<Integer, HashSet<Integer>> index_inverted = new Hashtable<Integer, HashSet<Integer>>();

		for (int i = 0; i < session.size(); i++) {

			Integer i_index = new Integer(i);
			HashSet<Integer> set = new HashSet<Integer>();

			goals_index.put(i_index, set);

			for (int j = i + 1; j < session.size(); j++) {

				if (areQueriesOnTheSameGoal(session.get(i), session.get(j))) {

					Integer j_index = new Integer(j);
			
					goals_index.get(i_index).add(j_index);
					
					//System.out.println("i: " + i + "\t"+ "j: "+ j);
					//System.out.println( session.get(i_index)[QUERY_POS] + "\t"+ session.get(j_index)[QUERY_POS]);

					if (index_inverted.containsKey(j_index)) {
						index_inverted.get(j_index).add(i_index);

					} else {
						HashSet<Integer> setI = new HashSet<Integer>();
						setI.add(i_index);
						index_inverted.put(j_index, setI);
					}

				} else {

					if (!index_inverted.containsKey(j)) {

						HashSet<Integer> setI = new HashSet<Integer>();

						index_inverted.put(j, setI);
					}
				}

			}
		}

		goals = getMergedGoals(goals_index, index_inverted, session);

		return goals;

	}

	static LinkedList<LinkedList<String[]>> getMergedGoals(
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted, LinkedList<String[]> session) {

		LinkedList<LinkedList<String[]>> goals = new LinkedList<LinkedList<String[]>>();

		Hashtable<Integer, HashSet<Integer>> merged_indexes = mergeGoalSets(indexes, indexInverted,session);

		Integer[] keys = (Integer[]) merged_indexes.keySet().toArray(
				new Integer[0]);
		Arrays.sort(keys);

		for (int i = 0; i < keys.length; i++) {

			Integer key = keys[i];
			HashSet<Integer> members = merged_indexes.get(key);

			Integer[] members_array = (Integer[]) members.toArray(new Integer[0]);
			Arrays.sort(members_array);

			LinkedList<String[]> list = new LinkedList<String[]>();
		//	list.add(session.get(key));
		
		
			for (int j = 0; j < members_array.length; j++) {

				Integer member = members_array[j];
			
				list.add(session.get(member));

			}

			goals.add(list);

		}
		return goals;

	}
	
	
	
	
	
	
	
	

	static Hashtable<Integer, HashSet<Integer>> mergeGoalSets(
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted, LinkedList<String[]> session) {

		Integer[] keys = (Integer[]) indexes.keySet().toArray(new Integer[0]);
		Arrays.sort(keys);

		HashSet<Integer> temporal = new HashSet<Integer>();

		Hashtable<Integer, HashSet<Integer>> indexes_merged = new Hashtable<Integer, HashSet<Integer>>();

		for (int i = 0; i < keys.length; i++) {

			Integer current = keys[i];
			if (!temporal.contains(current)) {
				temporal.add(current);
				HashSet<Integer> merged = new HashSet<Integer>();
				mergeHelper(current, indexes, indexInverted, temporal, merged);
				
				
			
				temporal.addAll(merged);
				merged.add(current);
				
				
				//	if(i==16){
					//printNewGroup(session,merged);
					
			//	}
				
				

				indexes_merged.put(current, merged);

			}

		}
		return indexes_merged;
	}
	
	private static void printNewGroup(LinkedList<String[]> session,
			HashSet<Integer> merged) {
		// TODO Auto-generated method stub
		
		
		System.out.println("--------------------------------------------------------");
		Iterator<Integer> iter= merged.iterator();
		while(iter.hasNext()){
			Integer i = iter.next();
			System.out.println(session.get(i)[QUERY_POS] + "\t" + i);
			
		}
		
	}


	private static void traceBack(
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer, HashSet<Integer>> indexInverted, HashSet<Integer> merged, Integer current,
			HashSet<Integer> temporal_back,HashSet<Integer> temporal) {
		// TODO Auto-generated method stub

		if (!indexInverted.containsKey(current))
			return;

		Iterator<Integer> iter = indexInverted.get(current).iterator();

		while (iter.hasNext()) {
			Integer back = iter.next();

			if (!temporal_back.contains(back)) {

				temporal_back.add(back);
				if(!temporal.contains(back)){
					
					merged.add(back);
					merged.add(current);
					temporal.add(back);
					mergeHelper(back,indexes,indexInverted,temporal,merged);
					
					
				}
				
				traceBack(indexes,indexInverted, merged, back, temporal_back,temporal);

			}

		}

	}
	
	
	
	private static void traceBackR(
			Hashtable<Long, HashSet<Long>> indexes,
			Hashtable<Long, HashSet<Long>> indexInverted, HashSet<Long> merged, Long current,
			HashSet<Long> temporal_back,HashSet<Long> temporal) {
		// TODO Auto-generated method stub

		if (!indexInverted.containsKey(current))
			return;

		Iterator<Long> iter = indexInverted.get(current).iterator();

		while (iter.hasNext()) {
			Long back = iter.next();

			if (!temporal_back.contains(back)) {

				temporal_back.add(back);
				if(!temporal.contains(back)){
					
					merged.add(back);
					merged.add(current);
					temporal.add(back);
					mergeHelperR(back,indexes,indexInverted,temporal,merged);
					
					
				}
				
				traceBackR(indexes,indexInverted, merged, back, temporal_back,temporal);

			}

		}

	}

	private static void mergeHelper(Integer current,
			Hashtable<Integer, HashSet<Integer>> indexes,
			Hashtable<Integer,HashSet<Integer>> indexInverted, HashSet<Integer> temporal, HashSet<Integer> merged) {

		// TODO Auto-generated method stub

		HashSet<Integer> set = indexes.get(current);
		HashSet<Integer> temporal_back = new HashSet<Integer>();
		Iterator<Integer> iter = set.iterator();

		merged.add(current);
		while (iter.hasNext()) {

			Integer next = iter.next();

			if (!temporal.contains(next)) {

			
				//merged.add(next);
				mergeHelper(next, indexes, indexInverted, temporal, merged);
				traceBack(indexes,indexInverted, merged, current,temporal_back, temporal);
				
				
				temporal.add(current);
				//merged.addAll(temporal_back);
				
				//temporal.add(current);
				//temporal.addAll(merged);
				//temporal.addAll(temporal_back);
			}

		}
		temporal_back.removeAll(temporal);
		merged.addAll(temporal_back);
	//	temporal.addAll(merged);
		
		

	}
	
	
	private static void mergeHelperR(Long current,
			Hashtable<Long, HashSet<Long>> indexes,
			Hashtable<Long,HashSet<Long>> indexInverted, HashSet<Long> temporal, HashSet<Long> merged) {

		// TODO Auto-generated method stub

		HashSet<Long> set = indexes.get(current);
		HashSet<Long> temporal_back = new HashSet<Long>();
		Iterator<Long> iter = set.iterator();

		merged.add(current);
		while (iter.hasNext()) {

			Long next = iter.next();

			if (!temporal.contains(next)) {

			
				//merged.add(next);
				mergeHelperR(next, indexes, indexInverted, temporal, merged);
				traceBackR(indexes,indexInverted, merged, current,temporal_back, temporal);
				
				
				temporal.add(current);
				//merged.addAll(temporal_back);
				
				//temporal.add(current);
				//temporal.addAll(merged);
				//temporal.addAll(temporal_back);
			}

		}
		temporal_back.removeAll(temporal);
		merged.addAll(temporal_back);
	//	temporal.addAll(merged);
		
		

	}

	/**
	 * Evaluate if two queries are part of the same user 'goal'
	 * 
	 * @param queryA
	 * @param queryB
	 * @return
	 */
	public static boolean areQueriesOnTheSameGoal(String[] queryA,
			String[] queryB) {

		String queryA_eval[] = new String[queryA.length];
		for (int i = 0; i < queryA.length; i++) {
			queryA_eval[i] = queryA[i];

		}

		queryA_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryA[QUERY_POS]);

		
	
		String queryB_eval[] = new String[queryB.length];
		
		

				
		for (int i = 0; i < queryB.length; i++) {

			queryB_eval[i] = queryB[i];

		}

		queryB_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryB[QUERY_POS]);

		int state = evaluateCurrentQuery(queryA_eval, queryB_eval);

		int edit_distance = StringAnalysis.getEditDistance(
				queryA_eval[QUERY_POS].replaceAll(" ", ""),
				queryB_eval[QUERY_POS].replaceAll(" ", ""));



		
		if (state == WORD_REMOVED || state == WORD_CHANGED
				|| state == MORE_RESULTS || state == WORD_ADDED)
			return true;

		// revise this -----------------------------------
		/*if (queryA_eval.length > URL_POS && queryB_eval.length > URL_POS) {

			if (queryA_eval[URL_POS].trim().equals(queryB_eval[URL_POS])) {

				return true;
			}
		}*/

		if (edit_distance <= EDIT_THRESHOLD) {
			return true;

		}

		return false;
	}
	
	
	public static boolean areQueriesOnTheSameGoal2(String[] queryA,
			String[] queryB) {

		
		
		
		String queryA_eval[] = new String[queryA.length];
		
		for (int i = 0; i < queryA.length; i++) {
			queryA_eval[i] = queryA[i];

		}

		queryA_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryA[QUERY_POS]);

		
	
		String queryB_eval[] = new String[queryB.length];
		
		
		
				
		for (int i = 0; i < queryB.length; i++) {

			queryB_eval[i] = queryB[i];

		}

		queryB_eval[QUERY_POS] = StringAnalysis
				.queryEntryNormalization(queryB[QUERY_POS]);

	//	int state = evaluateCurrentQuery(queryA_eval, queryB_eval);

		int edit_distance = StringAnalysis.getEditDistance(
				queryA_eval[QUERY_POS].replaceAll(" ", ""),
				queryB_eval[QUERY_POS].replaceAll(" ", ""));



		
		

		// revise this -----------------------------------
		/*if (queryA_eval.length > URL_POS && queryB_eval.length > URL_POS) {

			if (queryA_eval[URL_POS].trim().equals(queryB_eval[URL_POS])) {

				return true;
			}
		}*/

		if (queryA_eval[QUERY_POS].startsWith(queryB_eval[QUERY_POS])

		|| queryB_eval[QUERY_POS].startsWith(queryA_eval[QUERY_POS])

		) {
			
			return true;

		}
		
		if (queryA_eval[QUERY_POS].contains(queryB_eval[QUERY_POS])

				|| queryB_eval[QUERY_POS].contains(queryA_eval[QUERY_POS])

				) {
					
					return true;

				}
		
		
		
		if (edit_distance <= EDIT_THRESHOLD) {
			return true;

		}

		return false;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String aol = "/project/data/AOL_queryLOG/sessions_All.txt";

		// String goalPath =
		// "/home/sergio/projects/data/AOL_queryLOG/sessions_sorted.txt";
		String goalPath = "/home/sergio/projects/data/AOL_queryLOG/goals_containig_kids.txt";

		String goalIndex = "/home/sergio/projects/data/AOL_queryLOG/goal_index_kids.txt";
		// goalPath = "/project/data/AOL_queryLOG/goals_test1.txt";

		// String aol =
		// "/home/sergio/projects/data/AOL_queryLOG/sessions_All.txt";
		// String path = "/home/sergio/projects/data/dmoz/kt/kt-content.rdf.u8";
		// String
		// goalPath="/home/sergio/projects/data/AOL_queryLOG/sessions_contains_mteensCleaned.txt";
		// getStateTransitionMatrix(goalPath);
		// String
		// goalPath="/project/data/AOL_queryLOG/sessions_contains_mteensCleaned.txt";
		// String
		goalPath = "/home/sergio/projects/data/AOL_queryLOG/goals_containing_kidsR.txt";

		// getGoals(goalPath,false);

		// shallowClustering(readGoals(goalPath));
		String path = "/home/sergio/projects/data/delicious/experiments/dmoz_approx_tags1.txt";
		// path = "/home/sergio/projects/data/delicious/experiments/sample.txt";
		LinkedList<String[]> list = getDeliciousTags(path);
		LinkedList<LinkedList<String[]>> goals = getGoalsSimple(list);
		printGoals(goals);

		// mergeGoalSets_R(goalPath,goalIndex);

	}

	public static void shallowClustering(Hashtable<Long, Goal> hash) {

		Long index = 0l;

		Hashtable<Long, HashSet<Long>> indexes = new Hashtable<Long, HashSet<Long>>();
		Hashtable<Long, HashSet<Long>> indexInverted = new Hashtable<Long, HashSet<Long>>();

		boolean flag = true;
		while (flag && index < hash.size()) {

			HashSet<Long> set = new HashSet<Long>();

			Long j = index + 1;
			// indexes.put(index, set);

			while (j < hash.size()) {
				// System.out.println("i:" + index + "\t"+ "j:" +j);

				if (areGoalsEquivalent(hash.get(index), hash.get(j))) {

					set.add(j);
					
					
				//	System.out.println(index + "\t" + j);
					/*
					 * if (indexInverted.containsKey(j)) {
					 * 
					 * HashSet<Long> temporal = indexInverted.get(j);
					 * temporal.add(index);
					 * 
					 * } else {
					 * 
					 * HashSet<Long> temporal = new HashSet<Long>();
					 * 
					 * temporal.add(index);
					 * 
					 * indexInverted.put(j, temporal);
					 * 
					 * }
					 */

				}

				j++;
			}

			indexes.put(index, set);

			index++;
		}

		// print table

		Enumeration<Long> enu = indexes.keys();

		while (enu.hasMoreElements()) {

			Long key = enu.nextElement();
			HashSet<Long> set = indexes.get(key);

			Iterator<Long> iter = set.iterator();

			System.out.print(key);
			while (iter.hasNext()) {

				System.out.print("\t" + iter.next());

			}
			System.out.println("");

		}
	}
	
	private static boolean areGoalsEquivalent(Goal goal, Goal goal2) {
		// TODO Auto-generated method stub

		

		int threshold = 3;

		for (int k = 0; k < threshold; k++) {

			int l = ((int) (Math.random() * 10)) % goal.entries.size();

			
			int limit = Math.min(goal2.entries.size()/2+1, goal2.entries.size());
			
			for (int m = 0; m < limit; m++) {
				if (areQueriesOnTheSameGoal(goal.entries.get(l), goal2.entries
						.get(m))) {

					return true;

				}

			}

		}

		return false;
	}
	
	
	static Hashtable<Long, HashSet<Long>> mergeGoalSets_R(String path_goals,
			String path_index) {

		Hashtable<Long, Goal> hash = readGoals(path_goals);

		LinkedList<Hashtable<Long, HashSet<Long>>> index = readIndexes(path_index);
		
		Hashtable<Long, HashSet<Long>> indexes = index.get(0);
		Hashtable<Long, HashSet<Long>> indexInverted = index.get(0);

		Long[] keys = (Long[]) indexes.keySet().toArray(new Long[0]);
		Arrays.sort(keys);

		HashSet<Long> temporal = new HashSet<Long>();

		Hashtable<Long, HashSet<Long>> indexes_merged = new Hashtable<Long, HashSet<Long>>();

		for (int i = 0; i < keys.length; i++) {

			Long current = keys[i];
			if (!temporal.contains(current)) {
				temporal.add(current);
				HashSet<Long> merged = new HashSet<Long>();
				mergeHelperR(current, indexes, indexInverted, temporal, merged);

				temporal.addAll(merged);
				merged.add(current);
				System.out.print(current+ "\t");
				// if(i==16){
				// printNewGroup(session,merged);

				// }

				indexes_merged.put(current, merged);

			}

		}

		Long[] keys1 = (Long[]) indexes_merged.keySet().toArray(new Long[0]);
		Arrays.sort(keys1);
		LinkedList<LinkedList<String[]>> goals = new LinkedList<LinkedList<String[]>>();
		for (int i = 0; i < keys1.length; i++) {

			Long key = keys1[i];
			HashSet<Long> members = indexes_merged.get(key);

			Long[] members_array = (Long[]) members.toArray(new Long[0]);
			Arrays.sort(members_array);

			LinkedList<String[]> list = new LinkedList<String[]>();
			// list.add(session.get(key));

			for (int j = 0; j < members_array.length; j++) {

				Long member = members_array[j];

				list.addAll(hash.get(member).entries);

			}

			
			goals.add(list);
			
			


		}
		printGoals(goals);
	

		return indexes_merged;
	}

	private static LinkedList<Hashtable<Long, HashSet<Long>>> readIndexes(
			String pathIndex) {
		// TODO Auto-generated method stub

		LinkedList<Hashtable<Long, HashSet<Long>>> index = new LinkedList<Hashtable<Long, HashSet<Long>>>();
		Hashtable<Long, HashSet<Long>> indexes = new Hashtable<Long, HashSet<Long>>();

		Hashtable<Long, HashSet<Long>> i_indexes = new Hashtable<Long, HashSet<Long>>();

		FileInput in = new FileInput(pathIndex);

		String line = in.readString();
		while (line != null) {

			String t[] = line.trim().split("\t");

			HashSet<Long> set = new HashSet<Long>();

			for (int i = 1; i < t.length; i++) {

				set.add(new Long(t[i].trim()));

				if (i_indexes.containsKey(new Long(t[i].trim()))) {
					i_indexes.get(new Long(t[i].trim())).add(
							new Long(t[0].trim()));

				} else {

					HashSet<Long> temp = new HashSet<Long>();
					temp.add(new Long(t[0].trim()));
					i_indexes.put(new Long(t[i].trim()), temp);

				}

			}

			indexes.put(new Long(t[0]), set);
			line = in.readString();
		}

		
		index.add(indexes);
		index.add(i_indexes);
		return index;

	}

	
	
	public static LinkedList<String[]> getDeliciousTags(String path) {

		LinkedList<String[]> list = new LinkedList<String[]>();

		FileInput in = new FileInput(path);
		String line = in.readString();

		while (line != null) {

			String t[] = line.trim().split("\t");
			
			
			
			list.add(t);
			
			line = in.readString();
			
		}

		return list;

	}
	
	public static LinkedList<LinkedList<String[]>> getGoalsSimple(
			LinkedList<String[]> entries) {

		LinkedList<LinkedList<String[]>> list = new LinkedList<LinkedList<String[]>>();

		while (entries.size() > 0) {

			LinkedList<String[]> temp = new LinkedList<String[]>();
			temp.add(entries.get(0));

			for (int j = 1; j < entries.size(); j++) {

				if (entries.get(0).length > QUERY_POS
						&& entries.get(j).length > QUERY_POS
						&&

						areQueriesOnTheSameGoal2(entries.get(0), entries.get(j))) {

					temp.add(entries.get(j));

				}

				

			}

			list.add(temp);
			entries.removeAll(temp);

		}

		return list;
	}
	
	public static Hashtable<Long, Goal> readGoals(String path) {

		Hashtable<Long, Goal> hash = new Hashtable<Long, Goal>();

		FileInput in = new FileInput(path);

		String line = in.readString();

		String current = "";

		Goal goal = new Goal();
		long index = 0;
		while (line != null) {

			String t[] = line.trim().split("\t");

			String new_goal = t[0] + "-" + t[1];

			if (new_goal.equals(current)) {
				goal.entries.addLast(t);

			} else {

				goal = new Goal();
				goal.id = new_goal;
				goal.entries.addLast(t);
				goal.index = index;
		//		 System.out.println(index);
				index++;
				hash.put(goal.index, goal);

			}
			line = in.readString();
			current = new_goal;
		}

		return hash;
	}

}


class Goal{
	String id;
	LinkedList<String[]> entries = new LinkedList<String[]>();
	long index=0;
	
	
}

class ReformulationStat {

	long clickSkip = 0;
	long clickClick = 0;
	long skipClick = 0;
	long skipSkip = 0;

	long equalDomain = 0;

	float rank_difference=0;
	float time_difference=0;
	
	LinkedList<Long> rank = new LinkedList<Long>();
	LinkedList<Long> time = new LinkedList<Long>();

	long items = 0;
	
	long items_rank = 0;

}